package heap;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem = new int[10];
    }
    public void initElem(int[] array){  // 初始化数组
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void createMaxHeap(){  // 创建大根堆  时间复杂度为 O(N)
        for (int parent = (usedSize-2)/2; parent >= 0; parent--) {
            shiftDown(parent,usedSize);
        }
    }
    public void shiftDown(int parent, int len){  // 向下调整(从根向孩子调整)
        int child = 2 * parent + 1; // 至少有左孩子
        while (child < len) {
            if (child + 1 < len && elem[child] < elem[child+1]){
                child++;
            }
            if (elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    public void createMinHeap(){ // 创建小根堆
        for (int parent = (usedSize-2) / 2; parent >= 0; parent--){
            shiftDown2(parent,usedSize);
        }
    }
    public void shiftDown2(int parent, int len) {
        int child = 2 * parent + 1;
        while (child < len){
            if((child + 1) < len && elem[child] > elem[child+1]){
                child++;
            }
            if(elem[child] < elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    public void shiftUp(int child){  // 向上调整，用于向堆中添加元素
        int parent = (child - 1) / 2; // 向上调整建堆的时间复杂度O(N * logN)
        while (child > 0){
            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    public void offer(int val){  // 向堆中添加元素
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        shiftUp(usedSize-1);
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }
    public void pop(){
        if (isEmpty()){
            return;
        }
        int temp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = temp;
        usedSize--;
        shiftDown(0,usedSize);
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
    public int[] topK(int[] array, int k){  // Top K问题，n个数中，前k个最大的数
        int[] res = new int[k];
        if(array == null){
            return res;
        }
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            minHeap.offer(array[i]);
        }
        for (int i = k; i < array.length; i++) {
            if(minHeap.peek() < array[i]){
                minHeap.poll();
                minHeap.offer(array[i]);
            }
        }
        for (int i = 0; i < res.length; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }
    public void realizeMaxHeap(){  // 实现PriorityQueue的大根堆
        MaxHeap max = new MaxHeap();
        Queue<Integer> maxHeap = new PriorityQueue<>(max);
        maxHeap.offer(22);
        maxHeap.offer(29);
        maxHeap.offer(65);
        System.out.println(maxHeap.poll());
    }

}
class MaxHeap implements Comparator<Integer>{
    @Override
    public int compare(Integer i1, Integer i2) {
        return i2.compareTo(i1);
    }
}
